 #define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hash;
        for (int i = 0; i < nums.size(); i++)
        {
            int x = target - nums[i];
            if (hash.count(x)) return { hash[x], i };
            hash[nums[i]] = i;
        }

        return { -1, -1 };
    }
};

class Solution {
public:
    bool CheckPermutation(string s1, string s2) {
        if (s1.size() != s2.size()) return false;
        int hash[26] = { 0 };

        //1.遍历第一个数组，并对其对应字母数量进行计数
        for (auto s : s1)
            hash[s - 'a']++;

        //2.遍历第二个数组，对hash表进行对应字母--
        for (auto s : s2)
        {
            if (!hash[s - 'a'])
                return false;
            hash[s - 'a']--;
        }

        return true;
    }
};

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> hash;
        for (int x : nums)
            if (hash.count(x)) return true;
            else hash.insert(x);
        return false;
    }
};

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, int> hash;
        for (int i = 0; i < nums.size(); i++)
        {
            if (hash.count(nums[i]))
            {
                int x = i - hash[nums[i]];
                if (x <= k)
                    return true;
            }
            hash[nums[i]] = i;
        }

        return false;
    }
};

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> hash;

        //1.对所有字母异位词进行分组
        for (auto s : strs)
        {
            string tmp = s;
            sort(tmp.begin(), tmp.end());
            hash[tmp].push_back(s);
        }

        //2.提取所有字母异位词
        vector<vector<string>> ret;
        for (auto& [x, y] : hash)
        {
            ret.push_back(y);
        }

        return ret;
    }
};